# 面试题 10.03. 搜索旋转数组
# 一、题目描述
搜索旋转数组。给定一个排序后的数组，包含n个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。
示例1:
输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5 输出: 8（元素5在该数组中的索引）
示例2:
输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11 输出：-1 （没有找到）
提示:
- arr 长度范围在[1, 1000000]之间
# 二、题目解析
# 三、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 面试题 10.03. 搜索旋转数组：https://leetcode.cn/problems/search-rotate-array-lcci/
class Solution {
public int search(int[] arr, int target) {
/**
本题和 LeetCode 81、搜索旋转排序数组II 非常类似，只需要修改部分代码即可
修改位置标注了 星号
LeetCode 81、搜索旋转排序数组II 思路：https://r07na4yqwor.feishu.cn/docx/Pel3drtqMoBrHJxDT32ceMnCnMH
*/
// 重点：特殊情况处理
// 否则 [5,5,5,1,2,3,4,5]
// 5
// 这个测试用例会出错，预期结果是 0 ，下方代码输出的是 7
if(arr[0] == target){
return 0;
}
// left 指向当前区间的最左边位置，所以初始化为 0
int left = 0;
// right 指向当前区间的最右边位置，所以初始化为 arr.length - 1
int right = arr.length - 1;
// 循环进行二分查找，直到左端点位置超过了右端点
// 或者在循环过程中找到了 target
while( left <= right){
// 计算当前区间的中间位置，向下取整
int mid = (left + right) / 2;
// 如果中间位置数字 arr[mid] 等于目标值 target，那么说明找到了
// 返回当前的下标 mid
/***********************下方代码修改*********************************/
if(arr[mid] == target){
while (mid > 1 && arr[mid - 1] == arr[mid]) {
mid--;
}
return mid;
}
/***********************上方代码修改*********************************/
// 否则的话需要先确定 mid 的左边还是右边为有序区间
if(arr[left] == arr[mid]){
left++;
continue;
}
// 如果当前区间最左端的值 arr[left] 小于等于 arr[mid]
// 说明从 left 到 mid 这段区间是递增的，为有序区间
// 即 mid 的左侧为有序区间，右侧为无序区间
if(arr[left] < arr[mid]){
// 先去判断 target 是否在左侧有序区间内
// 如果目标值 target 大于这段有序区间的最小值 arr[left] 同时小于这段有序区间的最大值 arr[mid]
// 那么说明需要在这段有序区间去寻找 target
if(target >= arr[left] && target <= arr[mid]){
// 所以缩小范围为 left 到 mid - 1
// 当前区间的左侧为 left，右侧 right = mid - 1
right = mid - 1;
// 否则说明需要在 mid 的右侧无序区间搜索
}else{
// 所以缩小范围为 mid + 1 到 right
// 当前区间的左侧为 left = mid + 1，右侧 right
left = mid + 1;
}
// 否则说明当前区间最左端的值 arr[left] 大于 arr[mid]
// 说明从 left 到 mid 这段区间是无序区间
// 即 mid 的左侧为无序区间，右侧为有序区间
}else{
// 先去判断 target 是否在右侧有序区间内
// 如果目标值 target 大于这段有序区间的最小值 arr[mid] 同时小于这段有序区间的最大值 arr[right]
// 那么说明需要在这段有序区间去寻找 target
if(target >= arr[mid] && target <= arr[right]){
// 所以缩小范围为 mid + 1 到 right
// 当前区间的左侧为 left = mid + 1，右侧 right
left = mid + 1;
// 否则说明需要在 mid 的左侧无序区间搜索
}else{
// 所以缩小范围为 left 到 mid - 1
// 当前区间的左侧为 left，右侧 right = mid - 1
right = mid - 1;
}
}
}
/***********************下方代码修改*********************************/
return -1;
/***********************上方代码修改*********************************/
}
}